package base.search;

/**
 * 二分查找
 * https://www.cnblogs.com/kyoner/p/11080078.html
 * 二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。
 * 但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
 */
public class BinarySearch {

    public static int binarySearch(int[] srcArray, int target) {

        int start = 0;                                       //定义初始最小、最大索引
        int end = srcArray.length - 1;                       //确保不会出现重复查找，越界

        while (start <= end) {                               //计算出中间索引值

            int mid = (end + start)/2;                       //防止溢出

            if (target == srcArray[mid]) {
                return mid;                                 //判断下限
            } else if (target < srcArray[mid]) {
                end = mid - 1;                              //判断上限
            } else {
                start = mid + 1;
            }
        }

        return -1;                                            //若没有，则返回-1
    }

}
